package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 1589. 所有排列中的最大和
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/28 9:24
 */
public class MaxSumRangeQuery {

    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int length = nums.length;
        int[] counts = new int[length + 1];
        for (int[] request : requests) {
            counts[request[0]]++;
            counts[request[1] + 1]--;
        }
        for (int i = 1; i < length; i++) {
            counts[i] += counts[i - 1];
        }
        Arrays.sort(nums);
        Arrays.sort(counts);
        long sum = 0L;
        for (int i = 0; i < length; i++) {
            sum = (sum +  (long)nums[i] * counts[i + 1]) % 1000000007;
        }
        return (int) sum;
    }

}
